package dp;


/**
 * https://leetcode.cn/problems/longest-palindromic-substring/description/?favorite=2cktkvj
 */
public class _5_最长回文子串 {

    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) return s;
        // 初始化的maxLen等于其本身，一个字符串
        int maxLen = 1;
        int begin = 0;
        // dp表示dp[i][j] 表示i到j是否是回文子串
        boolean[][] dp = new boolean[s.length()][s.length()];

        for (int i = s.length() - 1; i >= 0; i--) {
            // 这边是j=i，不能j=i+1，否则dp[1][1]等不好记录了
            for (int j = i; j < s.length(); j++) {
                int len = j - i + 1;
                //  如果cs[i] == cs[j]，那么len小于2，dp[i][j]肯定是true
                if (s.charAt(i) == s.charAt(j)) {
                    if (len <= 2) {
                        dp[i][j] = true;
                    } else {
                        // cs[i] == cs[j]，那么dp[i][j] = dp[i + 1][j - 1]
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                    // i,j是回文子串，并且当前的len大于maxLen
                    if (dp[i][j] && len > maxLen) {
                        maxLen = len;
                        begin = i;
                    }
                }
            }
        }

        return s.substring(begin, begin + maxLen);
    }

}
